package com.example.leetdemo.process;

import java.util.*;

public class Solution310 {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> indexList = new ArrayList<>();
        if (n == 1) {
            indexList.add(0);
            return indexList;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            List<Integer> arr = map.getOrDefault(edges[i][0], new ArrayList<>());
            arr.add(edges[i][1]);
            map.put(edges[i][0], arr);

            List<Integer> arr1 = map.getOrDefault(edges[i][1], new ArrayList<>());
            arr1.add(edges[i][0]);
            map.put(edges[i][1], arr1);
        }
        int length = 10000007;
        for (int i = 0; i < n; i++) {
            Set<Integer> set = new HashSet<>();
            set.add(i);
            List<Integer> list = map.get(i);
            int l = 0;
            while (list.size() > 0) {
                l++;
                if (l > length) {
                    break;
                }
                List<Integer> next = new ArrayList<>();
                for (Integer j : list) {
                    if (!set.contains(j)) {
                        next.addAll(map.get(j));
                    }
                    set.add(j);
                }
                list = next;
            }
            if (l == length) {
                indexList.add(i);
            } else if (l < length) {
                indexList.clear();
                length = l;
                indexList.add(i);
            }
        }
        return indexList;
    }

    private List<Integer> findMinHeightTrees2(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n == 1) {
            result.add(0);
            return result;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            List<Integer> arr = map.getOrDefault(edges[i][0], new ArrayList<>());
            arr.add(edges[i][1]);
            map.put(edges[i][0], arr);

            List<Integer> arr1 = map.getOrDefault(edges[i][1], new ArrayList<>());
            arr1.add(edges[i][0]);
            map.put(edges[i][1], arr1);
        }

        return result;
    }

}
